package demo.DataStrucAndAlgo.Sort;

import java.util.Arrays;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/27-07-27-11:31
 * @Description：demo.DataStrucAndAlgo.Sort    归并排序   没有懂
 */
/*
归并排序
    分治思想，先将数据分段，再把每段排序合并。
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] data = {8,4,5,7,1,3,6,2};
        int[] temp = new int[data.length];
        mergeSort(data,0,data.length-1,temp);
        System.out.println(Arrays.toString(data));
    }

    public static void mergeSort(int[] data, int left, int right, int[] temp) {
        if(left < right){
            int mid = (left + right)/2;
            mergeSort(data,left,mid,temp);    //向左递归分解数组
            mergeSort(data,mid+1,right,temp);   // 向右递归分解数组
            merge(data,left,mid,right,temp);      //数据有序合并
        }
    }

    /**
     * 治阶段，合并有序数组，并将temp中的数据拷贝到原数组
     * @param data     分割后的原数组
     * @param left      左边起点索引
     * @param mid       中间索引
     * @param right     右边终止索引
     * @param temp      临时数组
     */
    public static void merge(int[] data, int left, int mid, int right, int[] temp) {
        int i = left;   //初始化i，i为左边部分遍历索引
        int j = mid + 1;  //初始化j，j为右边部分遍历索引
        int t = 0; //临时数组索引
        //数组有序合并
        //1、将左边和右边的数组按顺序填充到临时数组，直到有一组被取完
        while (i <= mid && j <= right){    //两边没有被取完
            //谁小谁先存
            if(data[i] < data[j]){
                temp[t] = data[i];
                i++;
                t++;
            }else{
                temp[t] = data[j];
                t++;
                j++;
            }
        }
        //将未取完的一种剩余的全部数据（有序）直接放入临时数组中
        while(i <= mid){    //左边的没取完
            temp[t] = data[i];
            i++;
            t++;
        }
        while(j <= right){
            temp[t] = data[j];
            j++;
            t++;
        }
        //把临时数组的数据拷贝到原数组
        t=0;
        int tempLeft = left;   //每次递归拷贝数组时，原数组起始拷贝位置都不相同，用变量代替
        while(tempLeft <= right){
            data[tempLeft] = temp[t];
            tempLeft++;
            t++;
        }
    }
}
